Tree DP

contents

트리 DP(동적 프로그래밍) 는 트리 자료 구조의 문제를 풀기 위해 사용되는 고급 알고리즘 설계 기법입니다. 이는 일반적으로 선형 구조(배열 등)나 그리드에서 사용되는 표준 동적 프로그래밍의 확장입니다.

트리 DP의 핵심 아이디어는, 트리의 문제를 해결하기 위해 먼저 그 서브트리(자식)에 대해 문제를 푼 다음, 그 결과들을 조합하는 것입니다. 이것이 가능한 이유는 트리가 최적의 부분 구조(문제의 해답이 더 작은, 독립적인 하위 문제의 해답에 의존함)와 중복되는 부분 문제(하위 문제가 여러 번 해결됨)를 가지고 있기 때문입니다.

🧠 작동 원리: 핵심 개념

트리 DP는 몇 가지 핵심 구성 요소에 의존합니다.

1. 순회: 깊이 우선 탐색 (DFS)

트리 DP는 거의 항상 깊이 우선 탐색(DFS)으로 구현됩니다. 순회는 루트에서 시작하여 모든 자식을 재귀적으로 방문합니다.

2. DP 상태: 후위 순회

부모 노드 u의 상태 dp[u]는 오직 그 모든 자식 노드들의 상태가 계산된 후에야 계산될 수 있습니다. 이는 실제 계산이 후위 순회(왼쪽, 오른쪽, 루트) 방식으로 일어난다는 것을 의미합니다.

비유: 조직도를 생각해 보세요. 관리자는 모든 직속 부하 직원들로부터 최종 판매 보고서(dp[child])를 받은 후에야 자신의 총 팀 판매량(dp[manager])을 파악할 수 있습니다.

3. dp[u] 상태 정의하기

이것이 모든 트리 DP 문제에서 가장 중요하고 창의적인 부분입니다. dp[u]는 노드 u를 루트로 하는 서브트리 문제에 대한 "해답"을 나타냅니다.

하지만 dp[u]가 항상 단일 숫자인 것은 아닙니다. dp[u]는 종종 부모가 자식에 대해 알아야 할 모든 정보를 나타내는 값들의 쌍이나 배열이어야 합니다. 일반적인 패턴은 dp[u][0] (노드 u를 제외한 해답)과 dp[u][1] (노드 u를 포함한 해답)입니다.

클래식 예제 1: 최대 독립 집합 (MIS)

독립 집합은 트리의 노드 집합 중 어떤 두 노드도 서로 인접하지 않은 집합입니다. MIS 문제는 가능한 가장 큰 독립 집합을 찾는 문제입니다.

1. 사고 과정

어떤 노드 u에 대해, 우리는 두 가지 선택을 할 수 있습니다.

1. u를 집합에 포함시키는 경우: u를 포함하면 1(u 자신)의 카운트를 얻습니다. 하지만, u의 직접적인 자식 노드들은 포함시킬 수 없습니다.
2. u를 집합에서 제외하는 경우: u를 제외하면, 각 자식 노드로부터 (자식을 포함하든 제외하든) 최선의 결과를 자유롭게 가져올 수 있습니다.

2. DP 상태

각 노드에 대해 두 가지 선택이 있으므로, DP 상태 dp[u]는 두 가지 값을 저장해야 합니다.

• dp[u][0]: u를 제외했을 때, u를 루트로 하는 서브트리의 MIS 크기.
• dp[u][1]: u를 포함했을 때, u를 루트로 하는 서브트리의 MIS 크기.

3. 점화식 ("문법")

DFS를 사용합니다. DFS가 자식 노드 v에서 _반환_될 때, u의 값을 계산하기 위해 v의 값(dp[v][0], dp[v][1])을 사용합니다.

• dp[u][1] 계산하기 (u를 포함하는 경우): 1(u 자신)을 더하고, 모든 자식들을 제외한 결과의 합을 더합니다. dp[u][1] = 1 + sum(dp[v][0] for v in children_of(u))
• dp[u][0] 계산하기 (u를 제외하는 경우): 각 자식으로부터 최선의 결과를 자유롭게 가져올 수 있습니다. 각 자식 v에 대해 v를 포함하는 경우(dp[v][1])와 v를 제외하는 경우(dp[v][0]) 중 더 큰 값을 선택합니다. dp[u][0] = sum(max(dp[v][0], dp[v][1]) for v in children_of(u))

4. 최종 답

DFS가 완료되어 전체 트리의 루트로 돌아온 후, 최종 답은 루트 노드의 두 가지 가능성 중 더 큰 값인 max(dp[root][0], dp[root][1])입니다.

클래식 예제 2: 트리의 지름

트리의 지름은 트리 내의 임의의 두 노드 사이의 가장 긴 경로입니다.

1. 사고 과정

어떤 노드 u에 대해, 그 서브트리 내의 가장 긴 경로는 다음 두 가지 중 하나일 수 있습니다.

1. 자식의 서브트리 중 하나에 완전히 포함된 경로.
2. u 자신을 "통과하는" 경로. 이 경로는 u의 자식들로부터 내려오는 가장 긴 두 개의 "아래 방향 경로"를 연결하여 형성됩니다.

2. DP 상태

여기서 DP 상태 dp[u]는 u에서 시작하여 그 서브트리 아래로 내려가는 가장 긴 경로의 길이가 됩니다.

3. 점화식

diameter를 전역 변수로 추적합니다. 후위 순회 DFS 중에 다음을 수행합니다.

1. diameter = 0으로 초기화합니다.
2. 노드 u에 대해, 모든 자식 v로부터의 결과를 봅니다. 자식 v를 통해 u에서 아래로 내려가는 가장 긴 경로는 1 + dp[v]입니다.
3. u의 자식들로부터 내려오는 가장 긴 두 개의 경로를 찾습니다. 이를 longest와 second_longest라고 부릅시다.
4. 전역 답 업데이트: u를 통과하는 가장 긴 경로는 longest + second_longest입니다. 전역 변수 diameter = max(diameter, longest + second_longest)를 업데이트합니다.
5. DP 상태 반환: 이 함수는 부모가 사용할 수 있도록 u에 대한 가장 긴 아래 방향 경로를 반환해야 합니다. 이는 longest입니다. 즉, dp[u] = longest입니다.

이 예는 반환 하는 값(dp[u])이 추적하는 답(diameter)과 다를 수 있음을 보여줍니다. DP 상태는 단지 부모가 필요로 하는 정보일 뿐입니다.

고급 기법: 루트 재지정 (Rerooting)

루트 재지정은 트리의 모든 노드 에 대해 상대적인 답을 요구하는 문제를 풀 때 사용되는 투-패스(two-pass) DP 기법입니다.

문제: "모든 노드 u에 대해, u에서 다른 모든 노드까지의 거리 합을 구하라."

단순한 해결책은 N개의 각 노드에서 전체 DFS를 실행하는 O(N^2) 복잡도를 갖습니다. 루트 재지정은 이를 O(N)에 해결합니다.

1. 패스 1: 표준 후위 순회 DFS

• 임의의 루트(예: 노드 0)를 선택합니다.
• DFS를 실행하여 모든 서브트리에 대한 DP 상태를 계산합니다.
• 이 문제의 경우 dp[u]는 두 가지를 저장할 수 있습니다.
  • subtree_size[u]: u의 서브트리에 있는 노드의 수.
  • subtree_sum[u]: u에서 자신의 서브트리 내의 다른 모든 노드까지의 거리 합.
• 점화식은 모든 자식 v에 대해 subtree_sum[u] = sum(subtree_sum[v] + subtree_size[v])입니다.

2. 패스 2: 전위 순회 DFS ("루트 재지정")

• 루트에서 (전위 순회) 새 DFS를 시작합니다.
• 부모는 자식에게 "트리의 나머지 부분"(즉, 자식의 서브트리 외부 에 있는 부분)에 대한 정보를 전달합니다.
• 부모 p에서 자식 c로 이동할 때, answer[p]와 1단계의 서브트리 정보를 사용하여 answer[c]를 계산할 수 있습니다.
• c에 대한 최종 답은 "아래 방향 답"(subtree_sum[c])과 "위 방향 답"(자신의 서브트리에 속하지 않는 모든 노드까지의 거리 합)의 합이며, 이 "위 방향 답"은 부모의 값으로부터 계산할 수 있습니다.

이 기법은 복잡하지만 "모든 노드에 대해" 푸는 문제들을 효율적으로 해결하는 데 매우 강력합니다.

references